//
//  MiaoPao.m
//  someAgorithm
//
//  Created by 樱桃李子 on 2020/9/12.
//  Copyright © 2020 peterlee. All rights reserved.
//

#import "MiaoPao.h"

@implementation MiaoPao

+ (void)sortSomeNumbers:(NSArray *)numbers{
    clock_t start = clock();
    if (numbers.count <= 0) {
        return;
    }
//    [MiaoPao sortWithMiaoPao:numbers];
//    [MiaoPao sortWithQuick:numbers];
    [MiaoPao sortWithChaRu:numbers];
    clock_t duration = clock() - start;
    NSLog(@"duration:%lu\nsecond=%.2lf",duration,(duration*1.0)/CLOCKS_PER_SEC);
}


/// MARK:冒泡排序法
/// @param numbers 要排序数组
+(void)sortWithMiaoPao:(NSArray *)numbers{
    NSMutableArray *temp = [numbers mutableCopy];
    for (int i = 0; i < temp.count; i++) {
        for (int j = i+1; j<temp.count; j++) {
            if ([temp[i] intValue] > [temp[j] intValue]) {
                [MiaoPao swapNumbers:temp A:i B:j];
                NSLog(@"%d==%@ %d==%@",i,temp[i],j,temp[j]);
                
            }
        }
    }
    NSLog(@"%@",temp);
}



/// MARK: 选择排序法
/// @param numbers 要排序数组
+(void)sortWithXuanZhe:(NSArray *)numbers{
    NSMutableArray *temp = [numbers mutableCopy];
       for (int i = 0; i < temp.count; i++) {
           for (int j = i+1; j<temp.count; j++) {
               if ([temp[i] intValue] > [temp[j] intValue]) {
                   [MiaoPao swapNumbers:temp A:i B:j];
                   NSLog(@"%d==%@ %d==%@",i,temp[i],j,temp[j]);
               }
           }
       }
       NSLog(@"%@",temp);
}

///  MARK:快排序法 先去寻找基准值 然后筛选出基准值左右数据 通过递归的方式排序
/// @param numbers  要排序数组
+(void)sortWithQuick:(NSArray *)numbers{
    NSArray *temp = [MiaoPao quickSortNumbers:numbers];
    NSLog(@"sortWithQuick---%@",temp);
}

+(NSArray *)quickSortNumbers:(NSArray *)numbers{
    NSMutableArray *temp = [numbers mutableCopy];
    NSNumber *provit = temp[numbers.count/2];//去中间的数
    NSMutableArray *leftNumbers = [NSMutableArray array];
    NSMutableArray *rightNumbers = [NSMutableArray array];
    for (int i=0; i<numbers.count; i++) {
        if ([numbers[i] intValue]< [provit intValue]) {
            [leftNumbers addObject:numbers[i]];
        }else if([numbers[i] intValue]> [provit intValue]){
            [rightNumbers addObject:numbers[i]];
        }
    }
    [leftNumbers addObject:provit];
    if (numbers.count>2&&(leftNumbers.count > 0 || rightNumbers.count>0)) {
        if (leftNumbers.count>1) {
            leftNumbers =[[MiaoPao quickSortNumbers:[leftNumbers copy]] mutableCopy];
        }
        if (rightNumbers.count>1) {
            rightNumbers =[[MiaoPao quickSortNumbers:[rightNumbers copy]] mutableCopy];
        }
        
    }
    [leftNumbers addObjectsFromArray:rightNumbers];
    return [leftNumbers copy];
}


/// MARK: 插入排序法
/// @param numbers  要排序的数组
+(void)sortWithChaRu:(NSArray *)numbers{
    NSMutableArray *sortedNumbers = [NSMutableArray arrayWithCapacity:numbers.count];
    [sortedNumbers addObject:numbers.firstObject];
    
    for (int i=1; i<numbers.count; i++) {
        [MiaoPao insertNumber:numbers[i] ToSortedArray:sortedNumbers];
    }
    NSLog(@"sortWithChaRu-------%@",sortedNumbers);
}

/// MARK: 插入新数字到排好顺序的数组
/// @param number  要插入数字
/// @param numbers  排好序的数组
+(void)insertNumber:(NSNumber *)number ToSortedArray:(NSMutableArray *)numbers {
    //末尾法
    for (int i = numbers.count - 1; i>=0; i--) {
        ///一旦出现比当前值小的就直接加到后面
        if ([number intValue]>[numbers[i] intValue]) {
            if (i == numbers.count - 1) {
                [numbers addObject:number];
            }else{
                [numbers insertObject:number atIndex:i+1];
            }
            break;
        }else{
            if (i == 0) {
                [numbers insertObject:number atIndex:0];
            }
        }
    }
}



+(void)swapNumbers:(NSMutableArray *)numbers A:(int)a B:(int)b{
    NSNumber *temp = numbers[a];
    [numbers replaceObjectAtIndex:a withObject:numbers[b]];
    [numbers replaceObjectAtIndex:b withObject:temp];
}

/// MARK: 随机指定个数的数据 范围默认0-100
/// @param count 随机个数
+(NSArray *)randomNumbers:(int)count{
    NSMutableArray *randomNumbers = [NSMutableArray arrayWithCapacity:count];
    for (int i = 0; i < count; i++) {
        NSNumber *random =[NSNumber numberWithInt:rand()%10000];
        [randomNumbers addObject:random];
    }
    NSLog(@"original numbers:%@",randomNumbers);
    return randomNumbers;
}



@end
